The present exemplary embodiment relates to determining shortest oceanic routes. It finds particular application in conjunction with routing a ship from one arbitrary point in the ocean X to another Y, and will be described with particular reference thereto. However, it is to be appreciated that the present exemplary embodiment is also amenable to other like applications.
A problem exists with the routing of a ship from one arbitrary point in the ocean X to another Y. The goal of routing a ship between arbitrary points is to quickly find the shortest route that does not run aground. In oceanic routing, the ocean is treated as a continuum. As such, it is not possible to make a list of all the possible values for various points X and Y in the ocean, together with a shortest route for each pair. Instead, the shortest route must be computed quickly once X and Y are discovered.
Our abstract Earth is a perfect sphere, has unit radius, and is cluttered with “obstacles” including land masses, coral reefs, shallow water depths, and the like. Each obstacle is represented by a polygon described by vertex points in clockwise order. All obstacles on Earth can be seen in their entirety by an observer located outside the Earth, and the word “clockwise” should be understood to be from the viewpoint of such an observer. These polygons (the interiors, to be precise) must be avoided in the process of getting from point X to point Y, hence the term obstacle. Points, like X and Y, that are the subject of shortest route calculations will be referred to as “location points”, such as “initial location point X” and “destination location point Y”.
Each pair of adjacent vertexes (i,j) on the border of an obstacle is connected by a segment of a great circle; this segment is the shortest distance between the two vertexes. Such great circle segments always have a length that is less than π, and will be referred to simply as “segments” in the following. The vertexes of the polygons are all assumed to be distinct, and it is also assumed that the polygons do not intersect or touch one another. It takes roughly 1000 vertexes to describe all of the obstacles on the Earth with sufficient detail for routing decisions.
For vertex i, the notations i.next and i.previous are utilized for the next and previous vertex as the obstacle is traversed in clockwise order. Thus, point Y is “visible” from point X (or vice versa—the relationship is symmetric) if there is some segment (X,Y) connecting X to Y that does not include an interior point from any obstacle. That segment will be unique unless X and Y are antipodes.
The motivation for the present application relates to the resupply of US Naval ships at sea (a kind of Traveling Salesman problem). In those scenarios, thousands of shortest-route calculations must be done in a time insensible to a human, so speed in finding the shortest route is of the essence.
The present application provides a method and system that quickly determines the shortest oceanic route between X and Y, using an oceanic routing system including a computing device configured to execute instructions to calculate the shortest oceanic route from an initial location point X to a destination location point Y.